package solution.hard;

import java.util.Arrays;

/**
 * @Program: solution
 * @Description: leetcode-517. 超级洗衣机
 * @Author: Mr.Yiu
 * @CreatedTime: 2021-09-29 12:22
 * https://leetcode-cn.com/problems/super-washing-machines/
 **/
public class XiYiJi {
    public static void main(String[] args) {
//        int[] m = {1,0,5};//3
//        int[] m = {0,3,0};//2
//        int[] m = {0,2,0};//-1

//        int[] m = {100000,0,100000,0,100000,0,100000,0,100000,0,100000,0};//50000
//        int[] m = {0,4,12,0};
        /*int[] m = {61245,72404,702,78678,998,43980,32126,28967,90781,418,78399,95681,92750,45464,
                40508,25158,93005,7197,67004,70242,34972,22379,40987,83188,86889,288,20548,38550,
                32852,90294,78683,9899,39502,31169,33302,66437,73246,30373,98444,38928,5917,24018,
                18157,95998,88161,8349,44402,74575,15990,11388,62294,3548,47496,61949,48609,801,
                59198,8707,95165,78789,23104,68734,38305,20487,22265,18279,21379,90918,43159,66741,
                93898,98157,10799,95870,34018,11514,830,52846,38281,79338,11530,669,42886,91202,42856,
                38512,31321,46044,9142,69710,25613,51884,88328,5117,11530,21614,9472,889,37160,35951};*/
        int bs = 1;//倍数
        int[] m = new int[10*bs];
        for (int i = 0; i < 5*bs; i++) {
            m[i]=0;
            m[i+5*bs]=100000;
        }
        long start = System.currentTimeMillis();
        System.out.println(findMinMoves(m));
        System.out.println(System.currentTimeMillis() - start);
    }

    /*    假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。
    在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。
    给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。
    如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。


    输入：machines = [1,0,5]
    输出：3
    解释：
    第一步:    1     0 <-- 5    =>    1     1     4
    第二步:    1 <-- 1 <-- 4    =>    2     1     3
    第三步:    2     1 <-- 3    =>    2     2     2

    输入：machines = [0,3,0]
    输出：2
    解释：
    第一步:    0 <-- 3     0    =>    1     2     0
    第二步:    1     2 --> 0    =>    1     1     1

    输入：machines = [0,2,0]
    输出：-1
    解释：
    不可能让所有三个洗衣机同时剩下相同数量的衣物。*/


    public static int findMinMoves(int[] machines){
        int sum = 0;
        for(int num : machines)
            sum += num;
        if(sum % machines.length != 0)
            return -1;

        int target = sum / machines.length;
        int res = 0, balance = 0;
        for(int i = 0 ; i < machines.length; i ++){
            balance += machines[i] - target;
            res = Math.max(res, Math.max(machines[i] - target, Math.abs(balance)));
        }
        return res;

    }

    public static  int findMinMovesy(int[] machines){
        int l = machines.length;//洗衣机数量
        int total = 0;//衣服总数量
        for (int m:machines) {
            total += m;
        }

        int count = -1;//移动次数
        if(total%l==0){//可以均分
            count = 0;//初始化步数为0
            int avl = total/l;//每个洗衣机最终的衣服数量

            boolean flag = true;
            while (flag){
//                System.out.println(Arrays.toString(machines));
//                System.out.println("count="+count);
                flag = false;//while循环标记，在以下for循环中如果存在某个洗衣机的衣服不等于avl则赋值成true
                int yflj = 0;//遍历洗衣机里面的衣服，遍历过的洗衣机衣服累计数量
                for (int i = 0; i < l; i++) {
                    yflj += machines[i];
                    if (i == 0) {
                        if(machines[i] > avl){//右移
                            machines[i]--;
                            yflj--;
                            machines[i+1]++;
                            flag = true;
                        }
                    } else if (i == (l-1)){
                        if(machines[i] > avl){//左移
                            machines[i]--;
                            machines[i-1]++;
                            flag = true;
                        }
                    }else {
                        if (yflj > avl*(i+1)) {//衣服累计均值大于总均值，当前位置需要右移
                            if (machines[i] > 0) {
                                machines[i]--;
                                yflj--;
                                machines[i + 1]++;
                                flag = true;
                            }
                        } else if (yflj < avl*(i+1)) {//衣服累计均值小于总均值，当前位置需要左移
                            if (machines[i] > 0 && (yflj-machines[i]) < (avl*i)) {
                                machines[i]--;
                                machines[i - 1]++;
                                flag = true;
                            }
                        } else {
                            if (machines[i] > avl) {
                                if((yflj-machines[i]) < avl*i ){//左移
                                    machines[i]--;
                                    machines[i-1]++;
                                    flag = true;
                                }else {//右移
                                    machines[i]--;
                                    yflj--;
                                    machines[i + 1]++;
                                    flag = true;
                                }
                            }
                        }
                    }
                }
                if(flag) count++;//移动有效步数加1
            }
        }

        return count;
    }
}
